home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / info-service / wais / ir-book-sources / bool / hdriver.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-04-08  |  10.7 KB  |  379 lines
  1. /***************************  driver.c  **************************************
  2.  
  3.   Purpose:    Test driver program for boolean operations code.
  4.  
  5.   Provenance:    Written and tested by S. Wartik, April 1991.
  6.  
  7.   Notes:    This module contains a main program and accompanying
  8.           subroutines that, when compiled, exercise every function
  9.         of the boolean operations module.  The testing is purely
  10.         in terms of the external interface that the boolean
  11.         operations module presents.  That is, the effects of
  12.         constructor functions are examined through the projector
  13.         functions.  This makes the code (almost) implementation-
  14.         independent.  For this reason, it may be used (with slight
  15.         modifications, controlled through #ifdef's) to test both
  16.         the bit-vector and the hashing implementations.
  17.         
  18.           Usage for the bit-vector version is:
  19.  
  20.             driver lower-bound upper-bound
  21.  
  22.         where the bounds specify the legal domain of the set.  In
  23.         the current implementation, abs(upper-bound - lower-bound)
  24.         must be less than 256.
  25.             
  26. **/
  27.  
  28. #include    <stdio.h>
  29.  
  30. #    include    "hash.h"
  31.  
  32. #define N_SETS        3
  33.  
  34. #define MIN_ELEMENTS    5        /* Make the tests "interesting". */
  35.                     /* Require at least 5 elements.     */
  36. int    hash(key)            /* Define the hashing function   */
  37.     elementType    key;        /* as the sum of the squares of  */
  38. {                    /* each bit's magnitude, base 3. */
  39.     int    i;
  40.     int    threePower;
  41.     int    sum;
  42.  
  43.     threePower = 1;
  44.     sum = 0;
  45.     for ( i = 0; i < 8*sizeof(elementType); i++ ) {
  46.         register int    bitValue;
  47.         bitValue = (key & 01)*threePower;
  48.         bitValue *= bitValue;
  49.         sum += bitValue;
  50.         threePower *= 3;
  51.     }
  52.  
  53.     return sum;
  54. }
  55.  
  56. boolean compare(v1, v2)
  57.     elementType    v1, v2;
  58. {
  59.     return v1 == v2;
  60. }
  61.  
  62.  
  63. void    Exit_If_Error_On();
  64. void    Exit_Indicating_Failed_Op();
  65.  
  66.  
  67. void    Test_Set_Operators();        /* The main routine is implemented  */
  68. void    Test_Union_Operators();        /* as a series of calls to several  */
  69. void    Test_Intersection_Operators();    /* procedures, each of which tests  */
  70. void    Test_Subtraction_Operators();    /* a particular aspect of the        */
  71. void    Test_Copy();            /* module.                */
  72. void    Test_Iterate();
  73.  
  74. boolean    Iterator();
  75.  
  76.  
  77. main(argc, argv)
  78.     int    argc;
  79.     char    *argv[];
  80. {
  81.     set    s[N_SETS];
  82.     int    lower, upper;
  83.     int    number_of_buckets;
  84.     int    i;
  85.  
  86.     if ( argc != 4 ) {
  87.         printf("Usage: %s lower-bound upper-bound number-of-buckets\n", argv[0]);
  88.         exit(1);
  89.     }
  90.  
  91.     lower = atoi(argv[1]);
  92.     upper = atoi(argv[2]);
  93.     if ( upper < lower+MIN_ELEMENTS ) {
  94.         printf("Please specify a set that can contain at least %d elements.\n",
  95.                MIN_ELEMENTS);
  96.         exit(1);
  97.     }
  98.     if ( (number_of_buckets = atoi(argv[3])) <= MIN_ELEMENTS ) {
  99.         printf("The 1st argument must be an integer >= %d.\n",
  100.                MIN_ELEMENTS);
  101.         exit(1);
  102.     }
  103.     
  104.  
  105.     for ( i = 0; i < N_SETS; i++ ) {    /* Test creation. */
  106.         Create(number_of_buckets, hash, compare, &s[i]);
  107.         Exit_If_Error_On("Create");
  108.     }
  109.     fputs("Creation works.\n", stdout);
  110.  
  111.     for ( i = 0; i < 2; i++ ) {        /* Test clearing sets. */
  112.         Clear(&s[i]);
  113.         Exit_If_Error_On("Clear");
  114.         if ( Empty(&s[i]) )
  115.             Exit_If_Error_On("Empty");
  116.         else    Exit_Indicating_Failed_Op("Empty");
  117.     }
  118.     fputs("Clearing works.\n", stdout);
  119.  
  120.     Test_Set_Operators(s, lower, upper);
  121.     fputs("Basic operators works.\n", stdout);
  122.     Test_Union_Operators(s, lower, upper);
  123.     fputs("Union works.\n", stdout);
  124.     Test_Intersection_Operators(s, lower, upper);
  125.     fputs("Intersection works.\n", stdout);
  126.     Test_Subtraction_Operators(s, lower, upper);
  127.     fputs("Subtraction works.\n", stdout);
  128.     Test_Copy(s, lower, upper);
  129.     fputs("Copying works.\n", stdout);
  130.     Test_Iterate(s, lower, upper);
  131.     fputs("Iterating works.\n", stdout);
  132.  
  133.     fputs("\nThe implementation passes.\n", stdout);
  134.     exit(0);
  135. }
  136.  
  137. void Test_Set_Operators(s, lower, upper)
  138.     set    s[];
  139.     int    lower, upper;
  140. {
  141.     int    i;
  142.     
  143.     for ( i = lower; i <= upper; i++ ) {    /* Test insertion of all    */
  144.         Insert(&s[0], i);        /* valid elements for a     */
  145.         Exit_If_Error_On("Insert");    /* set that doesn't already */
  146.         if ( Member(&s[0], i) )        /* contain them.        */
  147.             Exit_If_Error_On("Member");
  148.         else    Exit_Indicating_Failed_Op("Member");
  149.     }
  150.  
  151.     for ( i = lower; i <= upper; i++ ) {    /* Test insertion of all */
  152.         Insert(&s[0], i);        /* valid elements for a  */
  153.         Exit_If_Error_On("Insert");    /* set that already has  */
  154.         if ( Member(&s[0], i) )        /* them.         */
  155.             Exit_If_Error_On("Member");
  156.         else    Exit_Indicating_Failed_Op("Member");
  157.     }
  158.  
  159.     for ( i = lower; i <= upper; i++ ) {    /* Test deletion of all  */
  160.         Delete(&s[0], i);        /* valid elements when   */
  161.         Exit_If_Error_On("Delete");    /* the set already has     */
  162.         if ( ! Member(&s[0], i) )    /* them.         */
  163.             Exit_If_Error_On("Delete");
  164.         else    Exit_Indicating_Failed_Op("Member");
  165.     }
  166.  
  167.     for ( i = lower; i <= upper; i++ ) {    /* Test deletion of all  */
  168.         Delete(&s[0], i);        /* valid elements when   */
  169.         Exit_If_Error_On("Delete");    /* the set doesn't have     */
  170.         if ( ! Member(&s[0], i) )    /* them.         */
  171.             Exit_If_Error_On("Delete");
  172.         else    Exit_Indicating_Failed_Op("Member");
  173.     }
  174. }
  175.  
  176. void Test_Union_Operators(s, lower, upper)
  177.     set    s[];
  178.     int    lower, upper;
  179. {
  180.     int    i;
  181.  
  182.     Insert(&s[0], lower);            /* Test union of a set    */
  183.     Exit_If_Error_On("Insert");        /* with an empty set.      */
  184.     Unite(&s[0], &s[1], &s[2]);        /*   s2 <- {lower}U{}      */
  185.     Exit_If_Error_On("Unite");
  186.     if ( Member(&s[2], lower) )
  187.         Exit_If_Error_On("Member");
  188.     else    Exit_Indicating_Failed_Op("Member|Unite");
  189.     for ( i = lower+1; i <= upper; i++ )
  190.         if ( Member(&s[2], i) )
  191.             Exit_Indicating_Failed_Op("Member|Unite");
  192.         else    Exit_If_Error_On("Member");
  193.  
  194.     Insert(&s[1], lower+1);            /* Test union of two non-    */
  195.     Exit_If_Error_On("Insert");        /* empty, non-intersecting   */
  196.     Unite(&s[0], &s[1], &s[2]);        /* sets.             */
  197.     Exit_If_Error_On("Unite");        /*   s2 <- {lower}U{lower+1} */
  198.     if ( Member(&s[2], lower) && Member(&s[2], lower+1) )
  199.         Exit_If_Error_On("Member");
  200.     else    Exit_Indicating_Failed_Op("Member|Unite");
  201.     for ( i = lower+2; i <= upper; i++ )
  202.         if ( Member(&s[2], i) )
  203.             Exit_Indicating_Failed_Op("Member|Unite");
  204.         else    Exit_If_Error_On("Member");
  205.  
  206.                     /* Test union of two non-empty,   */
  207.     Insert(&s[0], lower+1);        /* intersecting sets.          */
  208.     Exit_If_Error_On("Insert");    /*   s2 <- {lower,lower+1} U      */
  209.     Unite(&s[0], &s[1], &s[2]);    /*        {lower+1}      */
  210.     Exit_If_Error_On("Unite");
  211.     if ( Member(&s[2], lower) && Member(&s[2], lower+1) )
  212.         Exit_If_Error_On("Member");
  213.     else    Exit_Indicating_Failed_Op("Member|Unite");
  214.     for ( i = lower+2; i <= upper; i++ )
  215.         if ( Member(&s[2], i) )
  216.             Exit_Indicating_Failed_Op("Member|Unite");
  217.         else    Exit_If_Error_On("Member");
  218. }
  219.  
  220. void Test_Intersection_Operators(s, lower, upper)
  221.     set    s[];
  222.     int    lower, upper;
  223. {
  224.     int    i;
  225.  
  226.     Clear(&s[0]);
  227.     Clear(&s[1]);
  228.  
  229.     Insert(&s[0], lower);            /* Test intersection of a */
  230.     Exit_If_Error_On("Insert");        /* set with an empty set. */
  231.     Intersect(&s[0], &s[1], &s[2]);        /*   s2 <- {lower}^{}      */
  232.     Exit_If_Error_On("Intersect");
  233.     for ( i = lower; i <= upper; i++ )
  234.         if ( Member(&s[2], i) )
  235.             Exit_Indicating_Failed_Op("Member|Intersect");
  236.         else    Exit_If_Error_On("Member");
  237.  
  238.     Insert(&s[0], lower);            /* Test intersection of two    */
  239.     Exit_If_Error_On("Insert");        /* non-empty, non-intersecting */
  240.     Insert(&s[1], lower+1);            /* sets.                  */
  241.     Exit_If_Error_On("Insert");        /*   s2 <- {lower}^{lower+1}   */
  242.     Intersect(&s[0], &s[1], &s[2]);
  243.     Exit_If_Error_On("Intersect");
  244.     for ( i = lower; i <= upper; i++ )
  245.         if ( Member(&s[2], i) )
  246.             Exit_Indicating_Failed_Op("Member|Intersect");
  247.         else    Exit_If_Error_On("Member");
  248.  
  249.     Insert(&s[0], lower);            /* Test intersection of two non- */
  250.     Exit_If_Error_On("Insert");        /* non-empty, intersecting sets. */
  251.     Insert(&s[0], lower+1);            /*   s2 <- {lower,lower+1}^         */
  252.     Exit_If_Error_On("Insert");        /*          {lower,lower+2}    */
  253.     Clear(&s[1]);
  254.     Insert(&s[1], lower);
  255.     Exit_If_Error_On("Insert");
  256.     Insert(&s[1], lower+2);
  257.     Exit_If_Error_On("Insert");
  258.     Intersect(&s[0], &s[1], &s[2]);
  259.     Exit_If_Error_On("Intersect");
  260.     if ( Member(&s[2], lower) )
  261.         Exit_If_Error_On("Member");
  262.     else    Exit_Indicating_Failed_Op("Member|Intersect");
  263.     for ( i = lower+1; i <= upper; i++ )
  264.         if ( Member(&s[2], i) )
  265.             Exit_Indicating_Failed_Op("Member|Intersect");
  266.         else    Exit_If_Error_On("Member");
  267. }
  268.  
  269. void Test_Subtraction_Operators(s, lower, upper)
  270.     set    s[];
  271.     int    lower, upper;
  272. {
  273.     int    i;
  274.  
  275.     Clear(&s[0]);                /* Subtract one empty set   */
  276.     Clear(&s[1]);                /* from another.        */
  277.     Subtract(&s[0], &s[1], &s[2]);
  278.     Exit_If_Error_On("Subtract");
  279.     for ( i = lower; i <= upper; i++ )
  280.         if ( Member(&s[2], i) )
  281.             Exit_Indicating_Failed_Op("Member|Subtract");
  282.         else    Exit_If_Error_On("Member");
  283. /*
  284. /* Added by Chris Fox to increase branch coverage
  285. */
  286.     Insert(&s[0], lower);            /* Test subtraction of two non-  */
  287.     Exit_If_Error_On("Insert");        /* non-empty, intersecting sets. */
  288.     Insert(&s[0], lower+1);            /*   s2 <- {lower,lower+1}-         */
  289.     Exit_If_Error_On("Insert");        /*          {lower,lower+2}    */
  290.     Clear(&s[1]);
  291.     Insert(&s[1], lower);
  292.     Exit_If_Error_On("Insert");
  293.     Insert(&s[1], lower+2);
  294.     Exit_If_Error_On("Insert");
  295.     Subtract(&s[0], &s[1], &s[2]);
  296.     Exit_If_Error_On("Intersect");
  297.     if ( Member(&s[2], lower+1) )
  298.         Exit_If_Error_On("Member");
  299.     else    Exit_Indicating_Failed_Op("Member|Subtract");
  300.     if ( Member(&s[2], lower) )
  301.         Exit_Indicating_Failed_Op("Member|Subtract");
  302.         else    Exit_If_Error_On("Member");
  303.     for ( i = lower+2; i <= upper; i++ )
  304.         if ( Member(&s[2], i) )
  305.             Exit_Indicating_Failed_Op("Member|Intersect");
  306.         else    Exit_If_Error_On("Member");
  307.  
  308. }
  309.  
  310. void Test_Copy(s, lower, upper)
  311.     set    s[];
  312.     int    lower, upper;
  313. {
  314.     int    i;
  315.     
  316.     Clear(&s[0]);                 /* Create a set with every */
  317.     for ( i = lower; i <= upper; i += 3 ) {     /* third possible value,   */
  318.         Insert(&s[0], i);         /* copy it, and make sure  */
  319.         Exit_If_Error_On("Insert");     /* both sets have the same */
  320.     }                     /* members.            */
  321.  
  322.     Copy(&s[0], &s[1]);
  323.  
  324.     for ( i = lower; i <= upper; i++ )
  325.         if ( Member(&s[0], i) != Member(&s[1], i) )
  326.             Exit_Indicating_Failed_Op("Member|Copy");
  327.         else    Exit_If_Error_On("Member");
  328. }
  329.  
  330. int    Count_Of_Elements_Iterated_Over;
  331.  
  332. boolean Iterator(e)
  333.     int    e;
  334. {
  335.     if ( e % 2 != 0 )    /* passed a value that wasn't inserted. */
  336.         Exit_Indicating_Failed_Op("Iterate");
  337.     Count_Of_Elements_Iterated_Over++;
  338.     return TRUE;
  339. }
  340.  
  341. void Test_Iterate(s, lower, upper)
  342.     set    s[];
  343.     int    lower, upper;
  344. {
  345.     int    i;
  346.     int    Count_Of_Elements_Added;
  347.  
  348.     Count_Of_Elements_Added = Count_Of_Elements_Iterated_Over = 0;
  349.  
  350.     Clear(&s[0]);
  351.     for ( i = (lower/2)*2 + 2; i <= upper; i += 2 ) {
  352.         Insert(&s[0], i);        /* Insert all even values */
  353.         Exit_If_Error_On("Insert");    /* (except perhaps the      */
  354.         Count_Of_Elements_Added++;    /* first) into the set.   */
  355.     }
  356.  
  357.     Iterate(&s[0], Iterator);
  358.     Exit_If_Error_On("Iterate");
  359.     if ( Count_Of_Elements_Added != Count_Of_Elements_Iterated_Over )
  360.         Exit_Indicating_Failed_Op("Iterate");
  361. }
  362.  
  363. void Exit_If_Error_On(operation)
  364.     char    operation[];
  365. {
  366.     if ( ! Error_Occurred() )
  367.         return;
  368.     printf("%s operation caused an error.\n", operation);
  369.     exit(1);
  370. }
  371.  
  372.  
  373. void Exit_Indicating_Failed_Op(operation)
  374.     char    operation[];
  375. {
  376.     printf("%s operation failed to function correctly.\n", operation);
  377.     exit(1);
  378. }
  379.